/*
 * @lc app=leetcode.cn id=154 lang=cpp
 *
 * [154] 寻找旋转排序数组中的最小值 II
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int find(const vector<int> &nums, int l, int r, int ans)
    {
        while (l <= r)
        {
            int mid = l + (r - l) / 2;
            if (mid == l)
            {
                ans = min(min(ans, nums[l]), nums[r]);
                l = mid + 1;
                break;
            }
            if (nums[mid] > nums[l])
            {
                //l至mid递增
                ans = min(ans, nums[l]);
                l = mid + 1;
            }
            else if(nums[mid] < nums[l])
            {
                //mid至r单调递增
                ans = min(ans, nums[mid]);
                r = mid - 1;
            }
            else
            {
                //无法判断递增关系
                ans = min(nums[mid], ans);
                ans = min(find(nums, l, mid - 1, ans), find(nums, mid + 1, r, ans));
                break;
            }
        }
        return ans;
    }
    int findMin(vector<int> &nums)
    {
        return find(nums, 0, nums.size() - 1, nums[0]);
    }
};
// @lc code=end
